import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int minPath=0;
        int[][] dp=new int[matrix.length+1][matrix[0].length+1];
        //第一列和第一行需要单独处理
        dp[0][0]=matrix[0][0];
        for(int i=1;i<matrix[0].length;i++){//1行
dp[0][i]=matrix[0][i]+dp[0][i-1];
        }
        for(int j=1;j<matrix.length;j++){//1列
dp[j][0]=matrix[j][0]+dp[j-1][0];
        }
        for(int i=1;i<matrix.length;i++){
            for(int j=1;j<matrix[0].length;j++){
                dp[i][j]+=Math.min(dp[i-1][j],dp[i][j-1])+matrix[i][j];
            }
        }
        return dp[matrix.length-1][matrix[0].length-1];

    }
}